package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
	
	You may assume the two numbers do not contain any leading zero, except the number 0 itself.
	
	Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)		
	Output: 7 -> 0 -> 8
		即：342+465=807
题目大意
	给定两个链表分别代表两个非负整数。数位以倒序存储，并且每一个节点包含一位数字。将两个数字相加并以链表形式返回。
解题思路
	
 * @Date 2017-09-15 00：42
 */
public class _002_Add_Two_Numbers {
	public static class ListNode {
		public int val;
		public ListNode next = null;
		ListNode() {}
		ListNode(int x) {val = x;}
	}
	
	private static  ListNode newLinkList1() {
		ListNode root = new ListNode(2);
		root.next = new ListNode(4);
		root.next.next = new ListNode(3);
		return root;
	}
	
	private static  ListNode newLinkList2() {
		ListNode root = new ListNode(5);
		root.next = new ListNode(6);
		root.next.next = new ListNode(4);
		return root;
	}


	/**
	 * @My:
	 * @param l1
	 * @param l2
	 * @return
	 */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	if (l1 == null && l2==null)	return null;
    	if (l1 == null || l2==null)	return l1==null ? l2 : l1;
    	ListNode p1 = l1, p2 = l2;
    	ListNode rs = new ListNode(-1), pRs = rs;	//结果链表, 尾插法插入节点
    	int flag = 0;							//是否需要进位 0..不需要, 1..进一位  
     
    	while (p1 != null && p2 != null) {
    		int sum = 0;
    		
    		ListNode pNew = new ListNode();
    		sum = p1.val + p2.val + flag;
    		if (sum >= 10) {
    			int diff = sum - 10;
    			pNew.val = diff;
    			flag = 1;
    		} else {
    			pNew.val = sum;
    			flag = 0;
    		}
    		pRs.next = pNew;
    		pRs = pRs.next;
    		p1 = p1.next;
    		p2 = p2.next;
    	}

    	/**
    	 * 存在一种情况，两个链表 不一样长(两个数位数不同 )，可能上面遍历完成 后，某链表还 留有部分()
    	 * 		eg：123+2：[3] [2] [1] + [2]	此时只有各位3和2得出5，高位的十位1和百位2都没计算 
    	 * 	这种情况就将剩余的链表(高位)全部加到结果链表尾部(还需考虑是否需要进位)(高位) [5][2][1] //2,1节点直接接在尾部
    	 */
    	ListNode pRemain = null;		//剩余元素
    	if (p1 != null)	pRemain = p1;
    	if (p2 != null)	pRemain = p2;
    	
    	//将剩余的节点全部加到pRs后
    	while (pRemain != null) {
    		int sum = pRemain.val + flag;
    		ListNode pNew = new ListNode(sum);
    		if (sum >= 10) {
    			int diff = sum - 10;
    			pNew.val = diff;
    			flag = 1;
    		} else {
    			pNew.val = sum;
    			flag = 0;
    		}
    		pRs.next = pNew;
    		pRs = pRs.next;
    		pRemain = pRemain.next;
    	}
    	
    	/**
    	 * eg: [5] + [5] 两个链表 遍历完后，留一个 进一
    	 */
    	if (flag > 0) {
    		ListNode pNew = new ListNode(1);
    		pRs.next = pNew;
    		pRs = pRs.next;
    		flag = 0;
    	}
    	
    	traverse("后", rs.next);
        return rs.next;
    }
    
    
    public void traverse(String tag, ListNode root) {
    	ListNode p = root;
    	while (p != null) {
    		LogUtils.print(tag+"^"+p.val);
    		p = p.next;
    	}
    	LogUtils.br();
    }
    
    
	public static void main(String[] args) {
		_002_Add_Two_Numbers obj = new _002_Add_Two_Numbers();
		obj.addTwoNumbers(obj.newLinkList1(), obj.newLinkList2());
	}

}
